P6271 [湖北省队互测2014]一个人的数论

注意本篇题解的 kk 是题目中的 dd

i=1n[gcd(i,n)=1]ik\sum_{i=1}^n[\gcd(i,n)=1]i^k

i=1nikdgcd(i,n)μ(d)\sum_{i=1}^ni^k\sum_{d|\gcd(i,n)}\mu(d)

dnμ(d)dki=1ndik\sum_{d|n}\mu(d)d^k\sum_{i=1}^{\lfloor \frac{n}{d} \rfloor}i^k

dnμ(d)dk(Sk(nd)+(nd)k)\sum_{d|n}\mu(d)d^k(S_k(\frac{n}{d})+(\frac{n}{d})^k)

dnμ(d)dkSk(nd)+dnμ(d)dk(nd)k\sum_{d|n}\mu(d)d^kS_k(\frac{n}{d})+\sum_{d|n} \mu(d)d^k(\frac{n}{d})^k

dnμ(d)dkSk(nd)+nkdnμ(d)\sum_{d|n}\mu(d)d^kS_k(\frac{n}{d})+n^k\sum_{d|n} \mu(d)

dnμ(d)dkSk(nd)+nk[n=1]\sum_{d|n}\mu(d)d^kS_k(\frac{n}{d})+n^k[n=1]

这道题 nn 肯定不为 11 , 后面的值为 00,只需考虑前一个和式。

自然数幂和是一个 k+1k+1 次多项式,可以用伯努利数算出系数,不妨记为 fif_i

由伯努利公式得:fk+1i=(k+1i)Bik+1f_{k+1-i}=\frac{\binom{k+1}{i}B_i}{k+1}

dnμ(d)dki=1k+1fi(nd)i\sum_{d|n}\mu(d)d^k \sum_{i=1}^{k+1} f_i \left ( \frac{n}{d} \right)^{i}

i=1k+1fidnμ(d)dk(nd)i\sum_{i=1}^{k+1} f_i\sum_{d|n}\mu(d)d^k \left( \frac{n}{d} \right)^{i}

i=1k+1finidnμ(d)dki\sum_{i=1}^{k+1} f_i n^i\sum_{d|n}\mu(d) d^{k-i}

后面的和式是一个积性函数,考虑质数取值

dpwμ(d)dki\sum_{d|p^w}\mu(d)d^{k-i}

i=0wμ(pi)pi(ki)\sum_{i=0}^w \mu(p^i)p^{i(k-i)}

μ\mu 的性质,只有 i=0i=011 时不为 00,所以上式等于 1pki1-p^{k-i}

所以我们能 O(w)\mathcal O(w) 计算出这个式子。

那么预处理出伯努利数和 ff ,原题便能 O(d2+dw)\mathcal O(d^2+dw) 解决了。

#include <cstdio>

const int MAXK = 105 , Mod = 1e9 + 7;

int Add( int x , int y ) { x += y; return x >= Mod ? x - Mod : x; }
int Sub( int x , int y ) { x -= y; return x < 0 ? x + Mod : x; }
int Mul( int x , int y ) { return 1ll * x * y % Mod; }
int Quick_pow( int x , int po ) { int Ans = 1; for( ; po ; po >>= 1 , x = Mul( x , x ) ) if( po & 1 ) Ans = Mul( Ans , x ); return Ans; }
int Inv( int x ) { return Quick_pow( x , Mod - 2 ); }
int Div( int x , int y ) { return Mul( x , Inv( y ) ); }

int fac[ MAXK + 10 ] , ivf[ MAXK + 10 ];
void Init( ) {
    fac[ 0 ] = 1;
    for( int i = 1 ; i <= MAXK + 5 ; i ++ ) fac[ i ] = Mul( fac[ i - 1 ] , i );
    ivf[ MAXK + 5 ] = Inv( fac[ MAXK + 5 ] );
    for( int i = MAXK + 5 ; i >= 1 ; i -- ) ivf[ i - 1 ] = Mul( ivf[ i ] , i );
}
int C( int n , int m ) { return Mul( fac[ n ] , Mul( ivf[ m ] , ivf[ n - m ] ) ); }

int w , k , p[ 1005 ] , a[ 1005 ];

int B[ MAXK + 5 ] , f[ MAXK + 5 ];
void Init_Bernoulli( ) {
    B[ 0 ] = 1;
    for( int i = 1 ; i <= MAXK ; i ++ ) {
        int Sum = 0;
        for( int j = 0 ; j < i ; j ++ ) Sum = Add( Sum , Mul( C( i + 1 , j ) , B[ j ] ) );
        B[ i ] = Sub( 0 , Mul( Sum , Inv( C( i + 1 , i ) ) ) );
    }
    for( int i = 0 ; i <= k ; i ++ ) f[ k + 1 - i ] = Div( Mul( C( k + 1 , i ) , B[ i ] ) , k + 1 );
}

int Sum( int pw ) {
    if( pw < 0 ) pw += Mod - 1;
    int Ans = 1;
    for( int i = 1 ; i <= w ; i ++ ) Ans = Mul( Ans , Sub( 1 , Quick_pow( p[ i ] , pw ) ) );
    return Ans;
}

int main( ) {
    scanf("%d %d",&k,&w);
    Init(); Init_Bernoulli();
    for( int i = 1 ; i <= w ; i ++ ) scanf("%d %d",&p[ i ],&a[ i ]);

    int Ans = 0 , n = 1;
    for( int i = 1 ; i <= w ; i ++ ) n = Mul( n , Quick_pow( p[ i ] , a[ i ] ) );
    for( int i = 1 , nk = 1 ; i <= k + 1 ; i ++ ) {
        nk = Mul( nk , n );
        Ans = Add( Ans , Mul( Mul( f[ i ] , nk ) , Sum( k - i ) ) );
    }
    printf("%d\n", Ans );
    return 0;
}